题面

莫名其妙翻到的 莫名其妙的题

解题思路

树链剖分+可持久化Trie

分析

应该也没有什么好分析的，这道数据结构的题没有多少思维量，直接看着做就好了，这里只是提供 树剖+可持久化Trie的板子而已

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define N 100003
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return (a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return (a>b)?a=b,1:0;}
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
struct node{
    int son[2],sum;
}T[N*31];
int ver[N<<1],nxt[N<<2],head[N],seg[N],top[N],rev[N];
int deep[N],size[N],fa[N],son[N],num;
int n,m,t,a[N],k,root[N],res,ans,l,r;
inline void add(rint x,rint y) {
    ver[++t]=y,nxt[t]=head[x],head[x]=t,
    ver[++t]=x,nxt[t]=head[y],head[y]=t;
}
inline void dfs1(rint k) {
    rint i,to;
    deep[k]=deep[fa[k]]+1,size[k]=1;
    for(i=head[k];i;i=nxt[i]) {
        to=ver[i];if(to==fa[k]) continue;
        fa[to]=k,dfs1(to),size[k]+=size[to];
        if(size[to]>size[son[k]]) son[k]=to;
    }
}
inline void dfs2(rint k) {
    if(son[k]) {
        seg[son[k]]=++num,
        top[son[k]]=top[k],
        rev[num]=son[k],
        dfs2(son[k]);
    }
    rint i,to;
    for(i=head[k];i;i=nxt[i]) {
        to=ver[i];if(top[to]) continue;
        seg[to]=++num,
        rev[num]=top[to]=to,dfs2(to);
    }
}
inline int Insert(rint pos,rint k) {
    rint i,c,x=root[pos]=++t,y=root[pos-1];T[x]=T[y];
    for(i=29;i>=0;--i) {
        c=k&(1<<i)?1:0;
        x=T[x].son[c]=++t,y=T[y].son[c],
        T[x]=T[y],++T[x].sum;
    }
}
inline void Query(rint x,rint y) {
    rint i,p=1,c;res=0;
    for(i=29;i>=0;--i) {
        c=k&(1<<i)?0:1;
        if(T[T[y].son[c]].sum-T[T[x].son[c]].sum)
            y=T[y].son[c],x=T[x].son[c],res+=1<<i;
        else y=T[y].son[c^1],x=T[x].son[c^1];
    }cmax(ans,res);
}
#define fx top[x]
#define fy top[y]
inline void Ask(rint x,rint y) {
    while(fx!=fy) {
        if(deep[fx]<deep[fy]) swap(x,y);
        Query(root[seg[fx]-1],root[seg[x]]);
        x=fa[fx];
    }
    if(deep[x]<deep[y]) swap(x,y);
    Query(root[seg[y]-1],root[seg[x]]);
}
int main()
{
    rint i,op;n=read(),m=read();
    for(i=1;i<=n;i++) a[i]=read();
    for(i=1;i<n;i++) k=read(),add(k,read());
    num=seg[1]=rev[1]=top[1]=1,
    dfs1(1),dfs2(1);
    for(i=1;i<=n;i++) Insert(i,a[rev[i]]);
    while(m--) {
        op=read(),l=read(),ans=0;
        if(op-1) r=read(),k=read(),Ask(l,r);
        else k=read(),Query(root[seg[l]-1],root[seg[l]+size[l]-1]);
        printf("%d\n",ans);
    }
    return 0;
}

devil.